import java.util.ArrayList;
import java.util.List;

//力扣45. 跳跃游戏 II
class Solution {
    public int jump(int[] nums) {
        //特殊情况:长度为1意味着0位置既是开始也是结束位置w
        if(nums.length==1){
            return 0;
        }

        int ans = 0;
        int i=0;

        while(i<nums.length){
            //这一步判断一般是 第一步就能到达结束位置 的
            if(nums[i]+i>=nums.length-1){
                return ans+1;
            }
            int j = i+1;
            int max = 0;
            int maxJump = i;

            while(j<=nums[i]+i&&j<nums.length){
                // 当前j位置能到达结束位置 break
                if(j+nums[j]>=nums.length-1){
                    maxJump = j;
                    break;
                }
                //寻找能到达的最远位置
                if(nums[j]+j>max){
                    maxJump = j;
                    max = nums[j]+j;
                }
                j++;
            }
            //这里说明原地踏步了，一般是下标为0的情况
            if(maxJump==i){
                return 0;
            }
            //跳到下一步,步数++
            i = maxJump;
            ans++;
            //当前位置能到达结束位置，直接步数++返回
            if(i+nums[i]>=nums.length-1){
                return ans+1;
            }
        }
        return ans;
    }
}



//力扣763. 划分字母区间
class Solution1 {
    public List<Integer> partitionLabels(String s) {
        List<Integer> ans = new ArrayList<>();
        char[] ch = s.toCharArray();
        int[] map = new int[26];

        // 记录每个字符最后出现的位置
        for (int i = 0; i < ch.length; i++) {
            char c = ch[i];
            map[c-'a'] = i;
        }

        int i = 0;
        while (i < ch.length) {
            int start = i;
            int maxLen = map[ch[i]-'a']; // 当前字符的最远位置
            int j = i + 1;

            // 扩展当前分段的边界
            while (j <= maxLen && j < ch.length) {
                maxLen = Math.max(maxLen, map[ch[j]-'a']);
                j++;
            }

            // 计算当前分段的长度并加入结果
            ans.add(maxLen - start + 1);

            // 更新i到下一个分段的起始位置
            i = maxLen + 1;
        }

        return ans;
    }
}

//198. 打家劫舍
class Solution2 {
    public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0]=nums[0];

        //当i=2时，dp[1]和dp[0]都是相邻的房子，按照题目要求不能同时偷窃相邻的房子，
        //所以dp[1]应该初始化为Math.max(nums[0], nums[1])。
        dp[1]= Math.max(nums[1],nums[0]);

        for(int i=2;i<nums.length;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.length-1];
    }
}